{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "colab_type": "text",
    "id": "view-in-github"
   },
   "source": [
    "<a href=\"https://colab.research.google.com/github/jermwatt/machine_learning_refined/blob/main/notes/4_Second_order_methods/4_4_Problems.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "osCJGNwQIuKm"
   },
   "source": [
    "## Chapter 4: Second order methods"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This notebook contains interactive content from an early draft of the university textbook <a href=\"https://github.com/neonwatty/machine-learning-refined/tree/main\">\n",
    "Machine Learning Refined (2nd edition) </a>.\n",
    "\n",
    "The final draft significantly expands on this content and is available for <a href=\"https://github.com/neonwatty/machine-learning-refined/tree/main/chapter_pdfs\"> download as a PDF here</a>."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "AoYm1wsGIuKn"
   },
   "source": [
    "# 4.4 Two Natural Weaknesses of Newton’s Method"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "ro5shiBvIuKo"
   },
   "source": [
    "Newton's method is a powerful algorithm that makes enormous progress towards at each step (unlike e.g., zero and first order methods that can require a huge number of steps to make equal progress).   However Newton's method suffers from two fundmanetal problems that limit its popularity in certain fields of machine learning, which we discuss here.  These problems involve its application to minimizing non-convex functions, and issues scaling with input dimension."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "pT3RRzOlIuKo"
   },
   "source": [
    "##  Application to minimizing non-convex functions"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "ScaAyDPPIuKp"
   },
   "source": [
    " As discussed in the previous Section, Newton's method can behave very badly when applied to minimizing non-convex functions.  Since each step is based off of the second order approximation to a function, if the curvature at a point is *convcave* Newton's method will naturally take a *step uphill*.  \n",
    " \n",
    "On the other hand because the second order approximation used by Newton's method contains so much local information than e.g., an analagous first order step, when applied to convex functions Newton's method can converge to a global minimum in far fewer steps - particularly when it is close to a minimum (since often the quadratic approximation matches a convex functions locally very well). "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "O5GOgwNfIuKp"
   },
   "source": [
    "##  Scaling limitations of Newton's method"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "ywK8UQalIuKp"
   },
   "source": [
    "A Newton's method step requires far more in terms of storage and computation than a first order step - requiring the storage and computation of not just a gradient but an entire $N\\times N$ Hessian matrix of second derivative information as well.  Simply storing the Hessian for a single step of Newton's method, with its $N^2$ entries, can quickly become challenging for what moderately sized input.  For example if the input to a function has dimension $N = 10,000$ the corresponding $10,000 \\times 10,000$ Hessian matrix has $10,000^2 = 100,000,000$ entries.  The kind of functions used in machine learning applications can easily have tens of thousands to hundreds of thousands or even hundreds of millions of inputs, making the complete storage of an associated Hessian impossible."
   ]
  }
 ],
 "metadata": {
  "colab": {
   "include_colab_link": true,
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.10"
  },
  "toc": {
   "colors": {
    "hover_highlight": "#DAA520",
    "navigate_num": "#000000",
    "navigate_text": "#333333",
    "running_highlight": "#FF0000",
    "selected_highlight": "#FFD700",
    "sidebar_border": "#EEEEEE",
    "wrapper_background": "#FFFFFF"
   },
   "moveMenuLeft": true,
   "nav_menu": {
    "height": "398px",
    "width": "252px"
   },
   "navigate_menu": true,
   "number_sections": false,
   "sideBar": true,
   "threshold": 4,
   "toc_cell": false,
   "toc_section_display": "block",
   "toc_window_display": false,
   "widenNotebook": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
